This invention relates to the field of network analysis, and in particular to network modeling.
The management of a complex network requires the use of tools that facilitate the analysis and diagnosis of network performance, and tools have been developed to ease this task. Many of the tools that have been developed for such analysis and diagnosis employ models of the networks to emulate/simulate the actual operations that occur within the network, or to predict performance parameters related to the expected performance of the network under a variety of conditions.
In order to effectively model the performance of a network, it is often necessary to model the physical topology of the network. For example, propagation delays are dependent on the geographic length of the communication paths, communications within local subnetworks avoid the access delays associated with wide-area networks, and so on.
In many cases, the ‘logical’ or ‘virtual’ connections that are created within a network obscure the physical topology of the network, and often the virtual structure of the network has little or no correspondence to the physical network. FIG. 1 illustrates an example network with routers 110 that provide connectivity between nodes on a local network 111 to remote nodes on other local networks 111. For ease of reference, the term router is used herein to identify any element of a network that is configured to affect or control the path that a packet takes as it is propagated from a source to a destination. That is, for example, a router includes any switching element that selects a path for the a packet, as well as any element that modifies a packet to affect the path that such a switching element may select, or any element that modifies the switching element based on packet content, and so on, wherein these elements may include hardware, software, firmware, or combinations thereof.
Physical connections 120 provide connectivity between the routers 110, and virtual connections 150 allow nodes on different physical networks 111 to appear to be members of the same subnetwork. In the example of FIG. 1, local networks 111a and 111b are connected via a virtual connection 150a. This virtual connection 150a conceals the fact that these networks 111a and 111b may be distant from each other, and conceals the actual physical path upon which messages will travel between networks 111a and 111b. From the network diagram of FIG. 1, it cannot be determined, for example, whether such messages will travel the path 120a-120b, or the path 120x-120y. 
In the Internet Protocol (IP) arena, IP tunnels are used to create virtual connections, to create Virtual Private Networks (VPN). FIG. 2 illustrates how messages that are addressed to remote nodes on a VPN are processed to effect the virtual connection. The IP packet 201 includes a data payload 211 and header information 210 that includes the destination address for the packet. In this example, the header information 210 would include the address of the destination within the virtual network. Commonly, this address is an IP private address (defined in the IP specification as addresses within particular ranges, such as addresses beginning with “10”, or “192.168”) that routers will recognize as being local, and are not to be routed beyond the local network.
Using IP tunneling, a router is configured to recognize an address as corresponding to a defined tunnel. Packets that are addressed to a tunneled VPN address 210 are encapsulated within an IP packet 202 by adding a second IP header 220 before the original header 210 in the VPN-addressed packet. The added tunnel IP header 220 includes the tunnel endpoint addresses, and the packet 202 may also include other tunnel information 221. When the packet 202 reaches the tunnel endpoint, the tunnel's IP header 220 and any additional tunnel information 221 is stripped off, producing a copy of the original VPN packet 201 with the original VPN address 210. This copy of the packet 201 is thereafter propagated at the local network at the tunnel endpoint in the same manner as it would have been propagated had it originated in the local network at the tunnel endpoint.
A common difficulty in network modeling is the modeling of IP tunnels, because the virtual private network is specifically provided to appear to be a local network, and the physical topology is masked. For a typical IP tunnel, the tunnel physical source and/or destination network interface may not be explicitly stated in the device configuration, and the tunnel configuration may lack source interface information, or refer to a logical source or destination loopback interface.
Another difficulty associated with the modeling of IP tunnels is the use of dynamic routing, wherein the physical topology may change based on changing configurations, device faults, and so on. Thus, even if a user defines the physical topology corresponding to an IP tunnel, dyamic routing may quickly render that defined topology obsolete.
Commonly, IP tunnels are used to provide a virtual path through a public network. In such a case, the actual physical path within the public network is unknown, and is generally modeled as a ‘black box’ or ‘cloud’, with physical input/output interfaces, but lacking details regarding the internals of the cloud. Although the physical model of the internals of such clouds is unavailable, the modeling of the network of interest, external to the clouds, often requires or benefits from knowing how the network is coupled to the clouds, including how each tunnel is physically coupled to each cloud.
Further compounding the difficulty of modeling IP tunnels is the use of dynamic tunnels wherein each tunnel is created on an ‘as needed’ basis.
It is an objective of this invention to provide a method and system that determines the actual physical source and destination interfaces used to carry tunnel data. It is a further objective of this invention to provide a method and system to determine the physical path between the tunnel endpoints.
These objectives, and others, are achieved by tracing through the device configuration and routing tables at the routers in a network to determine the outbound interface associated with each tunnel endpoint, and then inferring a likely return interface associated with the opposite tunnel endpoint. Depending upon the particular configurations, a variety of tests can be applied to validate the inference. Patricia trees are preferably used to store and process the configuration data for efficient tracing through the routing tables at each router.
Throughout the drawings, the same reference numerals indicate similar or corresponding features or functions. The drawings are included for illustrative purposes and are not intended to limit the scope of the invention.